/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package collectionutil;

import java.util.*;

/**
 *
 * @author NDA
 */
public class UtilImplement implements CollectionUtil {

    @Override
    public <T> void sort(List<T> list, Comparator<? super T> c) {
        T[] a = list.toArray((T[]) new Object[list.size()]);
        for (int i = 1; i < a.length; i++) {
            T v = a[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                if (c.compare(a[j],v) <= 0) {
                    break;
                }
                a[j + 1] = a[j];
            }
            a[j + 1] = v;
        }
        int i = 0;
        ListIterator< T> it = list.listIterator();
        while (it.hasNext()) {
            it.next();
            it.set(a[i++]);
        }
    }

    @Override
    public <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
        if (c == null) {
            return Collections.binarySearch(
                    (List< ? extends Comparable< ? super T>>) list, key);
        }
        if (!(list instanceof RandomAccess)) {
            ListIterator< ? extends T> it = list.listIterator();
            while (it.hasNext()) {
                int result;
                if ((result = -c.compare(it.next(), key)) <= 0) {
                    if (result == 0) {
                        return it.previousIndex();
                    }
                    return -it.previousIndex() - 1;
                }
            }
            return -list.size() - 1;
        }
        int low = 0, mid = list.size(), high = mid - 1, result = -1;
        while (low <= high) {
            mid = (low + high) >> 1;
            if ((result = -c.compare(list.get(mid), key)) > 0) {
                low = mid + 1;
            } else if (result == 0) {
                return mid;
            } else {
                high = mid - 1;
            }
        }
        return -mid - (result < 0 ? 1 : 2);
    }

    @Override
    public void reverse(List<?> list) {
        int size = list.size();
        ListIterator< Object> front = (ListIterator< Object>) list.listIterator();
        ListIterator< Object> back = (ListIterator< Object>) list.listIterator(size);
        for (int i = 0; i < size / 2; i++) {
            Object frontNext = front.next();
            Object backPrev = back.previous();
            front.set(backPrev);
            back.set(frontNext);
        }
    }

    @Override
    public void shuffle(List<?> list) {
        shuffle(list, new Random());
    }

    @Override
    public void shuffle(List<?> list, Random rnd) {
        @SuppressWarnings("unchecked")
        final List< Object> objectList = (List< Object>) list;
        if (list instanceof RandomAccess) {
            for (int i = objectList.size() - 1; i > 0; i--) {
                int index = rnd.nextInt(i + 1);
                objectList.set(index, objectList.set(i, objectList.get(index)));
            }
        } else {
            Object[] array = objectList.toArray();
            for (int i = array.length - 1; i > 0; i--) {
                int index = rnd.nextInt(i + 1);
                Object temp = array[i];
                array[i] = array[index];
                array[index] = temp;
            }
            int i = 0;
            ListIterator< Object> it = objectList.listIterator();
            while (it.hasNext()) {
                it.next();
                it.set(array[i++]);
            }
        }
    }

    @Override
    public void swap(List<?> list, int i, int j) {
        if (list == null) {
            throw new NullPointerException();
        }
        final int size = list.size();
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IndexOutOfBoundsException();
        }
        if (i == j) {
            return;
        }
        List< Object> rawList = (List< Object>) list;
        rawList.set(j, rawList.set(i, rawList.get(j)));
    }

    @Override
    public <T> void fill(List<? super T> list, T obj) {
        ListIterator< ? super T> it = list.listIterator();
        while (it.hasNext()) {
            it.next();
            it.set(obj);
        }
    }

    @Override
    public <T> void copy(List<? super T> dest, List<? extends T> src) {
        if (dest.size() < src.size()) {
            throw new ArrayIndexOutOfBoundsException("Source size does not fit into destination"); //$NON-NLS-1$
        }
        Iterator< ? extends T> srcIt = src.iterator();
        ListIterator< ? super T> destIt = dest.listIterator();
        while (srcIt.hasNext()) {
            try {
                destIt.next();
            } catch (NoSuchElementException e) {
                throw new ArrayIndexOutOfBoundsException("Source size does not fit into destination"); //$NON-NLS-1$
            }
            destIt.set(srcIt.next());
        }
    }

    @Override
    public <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {
        Iterator< ? extends T> it = coll.iterator();
        T min = it.next();
        while (it.hasNext()) {
            T next = it.next();
            if (comp.compare(min, next) > 0) {
                min = next;
            }
        }
        return min;
    }

    @Override
    public <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {
        Iterator< ? extends T> it = coll.iterator();
        T max = it.next();
        while (it.hasNext()) {
            T next = it.next();
            if (comp.compare(max, next) < 0) {
                max = next;
            }
        }
        return max;
    }

    @Override
    public void rotate(List<?> lst, int distance) {
        List< Object> list = (List< Object>) lst;
        int size = list.size();
        // Can't sensibly rotate an empty collection
        if (size == 0) {
            return;
        }
        // normalize the distance
        int normdist;
        if (distance > 0) {
            normdist = distance % size;
        } else {
            normdist = size - ((distance % size) * (-1));
        }
        if (normdist == 0 || normdist == size) {
            return;
        }
        if (list instanceof RandomAccess) {
            // make sure each element gets juggled
            // with the element in the position it is supposed to go to
            Object temp = list.get(0);
            int index = 0, beginIndex = 0;
            for (int i = 0; i < size; i++) {
                index = (index + normdist) % size;
                temp = list.set(index, temp);
                if (index == beginIndex) {
                    index = ++beginIndex;
                    temp = list.get(beginIndex);
                }
            }
        } else {
            int divideIndex = (size - normdist) % size;
            List< Object> sublist1 = list.subList(0, divideIndex);
            List< Object> sublist2 = list.subList(divideIndex, size);
            reverse(sublist1);
            reverse(sublist2);
            reverse(list);
        }
    }

    @Override
    public <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {

        int index;
        boolean found = false;
        while ((index = list.indexOf(oldVal)) > -1) {
            found = true;
            list.set(index, newVal);
        }
        return found;
    }

    @Override
    public int indexOfSubList(List<?> source, List<?> target) {
        int size = source.size();
        int sublistSize = target.size();
        if (sublistSize > size) {
            return -1;
        }
        if (sublistSize == 0) {
            return 0;
        }
        Object firstObj = target.get(0);
        int index = source.indexOf(firstObj);
        if (index == -1) {
            return -1;
        }
        while (index < size && (size - index >= sublistSize)) {
            ListIterator< ?> listIt = source.listIterator(index);
            if ((firstObj == null) ? listIt.next() == null : firstObj.equals(listIt.next())) {
                ListIterator< ?> sublistIt = target.listIterator(1);
                boolean difFound = false;
                while (sublistIt.hasNext()) {
                    Object element = sublistIt.next();
                    if (!listIt.hasNext()) {
                        return -1;
                    }
                    if ((element == null) ? listIt.next() != null : !element.equals(listIt.next())) {
                        difFound = true;
                        break;
                    }
                }
                if (!difFound) {
                    return index;
                }
            }
            index++;
        }
        return -1;
    }

    @Override
    public int lastIndexOfSubList(List<?> source, List<?> target) {

        int sublistSize = target.size();
        int size = source.size();
        if (sublistSize > size) {
            return -1;
        }
        if (sublistSize == 0) {
            return size;
        }
        Object lastObj = target.get(sublistSize - 1);
        int index = source.lastIndexOf(lastObj);
        while ((index > -1) && (index + 1 >= sublistSize)) {
            ListIterator< ?> listIt = source.listIterator(index + 1);
            if ((lastObj == null) ? listIt.previous() == null : lastObj.equals(listIt.previous())) {
                ListIterator< ?> sublistIt = target.listIterator(sublistSize - 1);
                boolean difFound = false;
                while (sublistIt.hasPrevious()) {
                    Object element = sublistIt.previous();
                    if (!listIt.hasPrevious()) {
                        return -1;
                    }
                    if ((element == null) ? listIt.previous() != null
                            : !element.equals(listIt.previous())) {
                        difFound = true;
                        break;
                    }
                }
                if (!difFound) {
                    return listIt.nextIndex();
                }
            }
            index--;
        }
        return -1;
    }

    @Override
    public <T> List<T> nCopies(int n, T o) {
        List<T> list = new ArrayList();
        for (int i = 0; i < n; i++) {
            list.add(o);
        }
        return list;
    }

    @Override
    public int frequency(Collection<?> c, Object o) {
        if (c == null) {
            throw new NullPointerException();
        }
        if (c.isEmpty()) {
            return 0;
        }
        int result = 0;
        Iterator< ?> itr = c.iterator();
        while (itr.hasNext()) {
            Object e = itr.next();
            if (o == null ? e == null : o.equals(e)) {
                result++;
            }
        }
        return result;
    }

    @Override
    public boolean disjoint(Collection<?> c1, Collection<?> c2) {
        if ((c1 instanceof Set) && !(c2 instanceof Set)
                || (c2.size()) > c1.size()) {
            Collection< ?> tmp = c1;
            c1 = c2;
            c2 = tmp;
        }
        Iterator< ?> it = c1.iterator();
        while (it.hasNext()) {
            if (c2.contains(it.next())) {
                return false;
            }
        }
        return true;
    }

    @Override
    public <T> boolean addAll(Collection<? super T> c, T... elements) {
        boolean modified = false;
        for (int i = 0; i < elements.length; i++) {
            modified |= c.add(elements[i]);
        }
        return modified;
    }
}